package test.algos.sorting.quicksort;

import java.util.List;
import java.util.Random;

import test.algos.sorting.SortUtil;

public class RandomPivot extends PivotChooser {

	protected Integer determinePivotIndex() {
		return randomSelect(computeMedian(), input);
	}

	private Integer computeMedian() {

		if (!input.isEmpty()) {
			int inputSize = input.size();
			if (inputSize > 1) {
				if ((inputSize % 2) == 0) {
					return inputSize / 2;
				} else {
					return (inputSize / 2) + 1;
				}
			}

		}
		return null;
	}

	private Integer randomSelect(int medianIndex, List<Integer> curInput) {

		if (!curInput.isEmpty()) {

			int randomPivotIndex = curInput.size() / 2;
			DivideStep divideStep = new DivideStep(curInput);
			Partitioner partitioner = new Partitioner(curInput);
			Integer chosenPivotIndex = partitioner.partition(randomPivotIndex);

			Integer compraeVal = SortUtil.compareAndReturn(chosenPivotIndex,
					medianIndex - 1);

			if (compraeVal != null) {
				divideStep.setPivotIndex(chosenPivotIndex);
				if (compraeVal == 0) {
					return chosenPivotIndex;
				} else if (compraeVal > 0) {
					return randomSelect(medianIndex, divideStep
							.getLeftPartition().getSubList());
				} else {
					return randomSelect(medianIndex - chosenPivotIndex,
							divideStep.getRightPartition().getSubList());
				}

			}
		}
		return null;
	}

}
